// Problem: 
// Contest: 
// URL: 
// Memory Limit: 
// Time Limit: 
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int dx[2]={0,1};
int dy[2]={1,0};
struct me
{
	int x,y,v;
	me(int xx,int yy,int vv)
	{
		x=xx,y=yy,v=vv;
	}
};
struct zh
{
	bool f;
	int v;
};
signed main()
{
	int n,m,ans;
	cin>>n>>m;
	vector<vector<int>> v(n+1,vector<int>(m+1));
	vector<vector<zh>> z(n+1,vector<zh>(m+1));
	//vector<vector<bool>> f(n+1,vector<bool>(m+1));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>v[i][j];
	ans=v[1][1];
	int t;
	cin>>t;
	vector<me> mes(t+1);
	for(int i=1;i<=t;i++)
	{
		cin>>mes[i].x>>mes[i].y>>mes[i].v;
		z[mes[i].x][mes[i].y].f=1;
		z[mes[i].x][mes[i].y].v=mes[i].v;
	}
		
	queue<me> q;
	q.push(me(1,1,0));
	while(!q.empty())
	{
		me tmp=q.front();
		q.pop();
		int x=tmp.x,y=tmp.y,v=tmp.v;
		for(int i=1;i<n;i++)
		{
			int xx=x+dx[i],yy=y+dy[i];
			if(xx>n||yy>m||(z[xx][yy].f==1&&z[xx][yy].v==v+1))continue;
			q.push(me(xx,yy,v+1));
		}
	}
	return 0;
}
